package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description:  260. Single Number III
 * @author: STU756
 * @create: 2020-08-16 22:08
 */
public class Pro0260 {
    public int[] singleNumber(int[] nums) {
        int sum1 = 0;
        for(int num : nums) sum1 ^= num;

        int k = 0;
        // 0 ^ 0 = 0, 1 ^ 1 = 0, 1 ^ 0 = 1  1^ 0 = 0 ^ 1= 1把a和b分开
        //sum1 = a ^ b, sum2 = a;
        while(((sum1 >>k) & 0x1) == 0) ++k;
        int sum2 = 0;
        //第k位为1的一组数，把a和b进行分开，分开两组
        for(int num: nums) {
            if( ((num >> k) & 1) == 1) {
                sum2 ^= num;
            }
        }
        return new int[]{sum2, sum1 ^ sum2};
    }
}
